package com.yanceysong.codetop.s11_s20;


public class S16_Easy_88_合并两个有序数组 {
    /**
     * S16_Easy_88_合并两个有序数组
     * <p>
     * <a href="https://leetcode.cn/problems/merge-sorted-array/">...</a>
     * <p>
     * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
     * <p>
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     * <p>
     * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
     * 为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
     * <p>
     * 解题思路：逆向双指针
     * 1. 由于 nums1 数组的后半部分是空的（值为0），我们可以利用这个空间，从后向前填充合并后的元素。
     * 2. 这样可以避免从前向后合并时需要移动 nums1 中原有元素的麻烦。
     * 3. 我们使用三个指针：
     * .   - `p1` 指向 nums1 的有效元素末尾（m-1）
     * .   - `p2` 指向 nums2 的末尾（n-1）
     * .   - `p` 指向 nums1 的最末尾（m+n-1）
     * 4. 比较 `nums1[p1]` 和 `nums2[p2]` 的大小，将较大的元素放到 `nums1[p]` 的位置，然后移动相应的指针。
     * 5. 循环直到 `p2` 小于 0，即 nums2 中的所有元素都已合并到 nums1 中。
     * <p>
     * 图解算法：
     * nums1 = [1, 2, 3, 0, 0, 0], m = 3
     * nums2 = [2, 5, 6],       n = 3
     * <p>
     * 初始状态:
     * .    p1 -> 3 (index 2)
     * .    p2 -> 6 (index 2)
     * .    p  -> 0 (index 5)
     * <p>
     * 比较 nums1[p1]=3 和 nums2[p2]=6, 6更大
     * nums1[p] = 6, p--, p2--
     * nums1 = [1, 2, 3, 0, 0, 6]
     * <p>
     * 比较 nums1[p1]=3 和 nums2[p2]=5, 5更大
     * nums1[p] = 5, p--, p2--
     * nums1 = [1, 2, 3, 0, 5, 6]
     * <p>
     * 比较 nums1[p1]=3 和 nums2[p2]=2, 3更大
     * nums1[p] = 3, p--, p1--
     * nums1 = [1, 2, 3, 3, 5, 6]
     * <p>
     * ...以此类推，直到 p2 < 0
     * <p>
     * 时间复杂度：O(m+n)，因为每个元素最多被访问一次。
     * 空间复杂度：O(1)，因为我们是原地修改，没有使用额外的存储空间。
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 初始化三个指针
        // pNums1 指向 nums1 的有效元素末尾
        int pNums1 = m - 1;
        // pNums2 指向 nums2 的末尾
        int pNums2 = n - 1;
        // insertPointer 指向 nums1 数组的最末尾，用于放置合并后的元素
        int insertPointer = m + n - 1;

        // 从后向前遍历 nums2 数组，当 nums2 的所有元素都合并完毕时，循环结束
        while (pNums2 >= 0) {
            // 比较 pNums1 和 pNums2 指向的元素，将较大的元素放入 insertPointer 的位置
            // 同时需要处理 pNums1 已经越界的情况
            if (pNums1 >= 0 && nums1[pNums1] > nums2[pNums2]) {
                // 如果 nums1 的元素更大，将其放入合并数组的末尾
                nums1[insertPointer] = nums1[pNums1];
                pNums1--; // nums1 的指针向前移动
            } else {
                // 如果 nums2 的元素更大或相等，或者 pNums1 已越界，将其放入合并数组的末尾
                nums1[insertPointer] = nums2[pNums2];
                pNums2--; // nums2 的指针向前移动
            }
            // 无论放置哪个元素，插入指针都需要向前移动
            insertPointer--;
        }
        // 循环结束后，如果 nums2 已经全部合并，而 nums1 还有剩余元素，
        // 它们已经在正确的位置，无需额外操作。
    }

    public static void main(String[] args) {
        S16_Easy_88_合并两个有序数组 solution = new S16_Easy_88_合并两个有序数组();

        System.out.println("=== 合并两个有序数组测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExample(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 特殊情况测试
        System.out.println("\n--- 测试3: 特殊情况测试 ---");
        testSpecialCases(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExample(S16_Easy_88_合并两个有序数组 solution) {
        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int[] nums2 = {2, 5, 6};
        int[] expected = {1, 2, 2, 3, 5, 6};
        testMerge(solution, nums1, 3, nums2, 3, expected, "题目示例");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S16_Easy_88_合并两个有序数组 solution) {
        // 测试1: nums2 为空
        int[] nums1_1 = {1};
        int[] nums2_1 = {};
        int[] expected1 = {1};
        testMerge(solution, nums1_1, 1, nums2_1, 0, expected1, "nums2 为空");

        // 测试2: nums1 为空
        int[] nums1_2 = {0};
        int[] nums2_2 = {1};
        int[] expected2 = {1};
        testMerge(solution, nums1_2, 0, nums2_2, 1, expected2, "nums1 为空");

        // 测试3: nums1 和 nums2 都为空
        int[] nums1_3 = {};
        int[] nums2_3 = {};
        int[] expected3 = {};
        testMerge(solution, nums1_3, 0, nums2_3, 0, expected3, "nums1 和 nums2 都为空");
    }

    /**
     * 测试特殊情况
     */
    private static void testSpecialCases(S16_Easy_88_合并两个有序数组 solution) {
        // 测试1: nums1 的元素都小于 nums2 的元素
        int[] nums1_1 = {1, 2, 3, 0, 0, 0};
        int[] nums2_1 = {4, 5, 6};
        int[] expected1 = {1, 2, 3, 4, 5, 6};
        testMerge(solution, nums1_1, 3, nums2_1, 3, expected1, "nums1 < nums2");

        // 测试2: nums1 的元素都大于 nums2 的元素
        int[] nums1_2 = {4, 5, 6, 0, 0, 0};
        int[] nums2_2 = {1, 2, 3};
        int[] expected2 = {1, 2, 3, 4, 5, 6};
        testMerge(solution, nums1_2, 3, nums2_2, 3, expected2, "nums1 > nums2");

        // 测试3: 包含重复数字
        int[] nums1_3 = {1, 2, 2, 0, 0, 0};
        int[] nums2_3 = {2, 2, 3};
        int[] expected3 = {1, 2, 2, 2, 2, 3};
        testMerge(solution, nums1_3, 3, nums2_3, 3, expected3, "包含重复数字");

        // 测试4: 包含负数
        int[] nums1_4 = {-3, -1, 0, 0, 0};
        int[] nums2_4 = {-2, 0};
        int[] expected4 = {-3, -2, -1, 0, 0};
        testMerge(solution, nums1_4, 2, nums2_4, 2, expected4, "包含负数");
    }

    /**
     * 测试合并数组的辅助方法
     */
    private static void testMerge(S16_Easy_88_合并两个有序数组 solution, int[] nums1, int m, int[] nums2, int n, int[] expected, String description) {
        // 打印测试前的输入状态
        System.out.print(description + " - 输入: nums1=" + java.util.Arrays.toString(nums1) + ", m=" + m + ", nums2=" + java.util.Arrays.toString(nums2) + ", n=" + n);

        // 执行合并操作
        solution.merge(nums1, m, nums2, n);

        // 打印输出和期望结果
        System.out.print(" -> 输出: " + java.util.Arrays.toString(nums1));
        System.out.println(" (期望: " + java.util.Arrays.toString(expected) + ")");

        // 断言验证结果
        assert java.util.Arrays.equals(nums1, expected) : description + " 测试失败";
    }
}

